package leetcode.editor.cn;

import java.util.*;

class RemoveInvalidParentheses {
    public static void main(String[] args) {
        Solution solution = new RemoveInvalidParentheses().new Solution();
        solution.removeInvalidParentheses(")(f");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // https://leetcode.cn/problems/remove-invalid-parentheses/solution/gong-shui-san-xie-jiang-gua-hao-de-shi-f-asu8/
    class Solution {
        // DFS + 回溯
        /*public List<String> removeInvalidParentheses(String s) {
            this.s = s;
            this.res = new HashSet<>();
            this.n = s.length();
            this.len = 0;

            int l = 0, r = 0;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == '(') l++;
                if (c == ')') r++;
            }
            this.max = Math.max(l, r);
            dfs("", 0, 0);
            return new ArrayList<>(res);
        }

        Set<String> res;
        String s;
        int max, n, len;

        // 使用score来代表左右括号数的得分
        // 左括号加一，右括号减一
        public void dfs(String cur, int idx, int score) {
            // 判断是否满足
            if (score < 0 || score > max) return;
            // 搜索到字符串的末尾
            if (idx == n) {
                // 如果分值为0，长度大于等于收集前面的最大长度
                if (score == 0 && cur.length() >= len) {
                    // 遇到更长的字符，clear掉前面所收集的所有字符
                    if (cur.length() > len) res.clear();
                    res.add(cur);
                    // 记录最长的字符
                    len = cur.length();
                }
                return;
            }

            char c = s.charAt(idx);
            // 括号可以放，也可以不放(代表要进行删除)，放入分值对应加一或者减一
            if (c == '(') {
                dfs(cur + c, idx + 1, score + 1);
                dfs(cur, idx + 1, score);
            } else if (c == ')') {
                dfs(cur + c, idx + 1, score - 1);
                dfs(cur, idx + 1, score);
            } else {
                // 字母直接放入，分值不变
                dfs(cur + c, idx + 1, score);
            }
        }*/

        // 剪枝
        // 我们可以通过预处理，得到最后的「应该删除的左括号数量」和「应该删掉的右括号数量」，来直接得到最终的 len。
        public List<String> removeInvalidParentheses(String s) {
            this.s = s;
            this.res = new HashSet<>();
            this.n = s.length();
            this.len = 0;

            int l = 0, r = 0;
            for (char c : s.toCharArray()) {
                if (c == '(') l++;
                if (c == ')') r++;
            }
            this.max = Math.max(l, r);

            int l1 = 0, r1 = 0; // l1, r1代表

            for (char c : s.toCharArray()) {
                if (c == '(') {
                    l1++;
                } else if (c == ')') {
                    if (l1 != 0) l1--;
                    else r1++;
                }
            }

            len = n - l1 - r1;

            dfs("", l1, r1, 0, 0);
            return new ArrayList<>(res);
        }

        Set<String> res;
        String s;
        int max, n, len;

        // 使用score来代表左右括号数的得分
        // 左括号加一，右括号减一
        public void dfs(String cur, int l, int r, int idx, int score) {
            if (l < 0 || r < 0 || score < 0 || score > max) return;
            if (l == 0 && r == 0) {
                if (cur.length() == len) res.add(cur);
            }
            if (idx == n) return;

            char c = s.charAt(idx);
            // 括号可以放，也可以不放(代表要进行删除)，放入分值对应加一或者减一
            if (c == '(') {
                dfs(cur + c, l, r, idx + 1, score + 1);
                dfs(cur, l - 1, r, idx + 1, score);
            } else if (c == ')') {
                dfs(cur + c, l, r, idx + 1, score - 1);
                dfs(cur, l, r - 1, idx + 1, score);
            } else {
                // 字母直接放入，分值不变
                dfs(cur + c, l, r, idx + 1, score);
            }
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
